1. Field of the Invention
The present invention generally relates to tracing of shorts in very large nets in Very Large Scale Integrated (VLSI) circuit designs and, more particularly, to efficiently finding one electrical path containing at least one of the VLSI design component instances causing the short using Breadth First Search (BFS) with optimal pruning.
2. Background Description
The problem of tracing shorts in a circuit design is to find an electrical path, consisting of a small number of VLSI design component instances, such that it contains at least one of the VLSI design component instances that cause the short. We refer to such a path in the following as a "shorting path". Shorts between large nets, e.g., between circuit ground (GND) and source voltage (VDD), occur frequently in designs. Although existing tools are able to detect the existence of a short in a hierarchical design, finding a shorting path in large designs is extremely time consuming. The automated tracing of shorts between very large nets by existing software tools typically fails due to extreme storage or computation time requirements.
The problem of finding a short electrical path between two VLSI design component instances with different net attributes can be mapped to finding a short path in a graph, in which the vertices correspond to VLSI design component instances and the edges correspond to direct electrical connectivity between the two adjacent vertices. Net attributes are names attached to at least one VLSI design component instance on a net, where a net is a set of VLSI design component instances which form a connected component with respect to a relation as, for example, intersection between geometric shapes of which the VLSI design components are composed. Geometric shapes are the most elementary type of VLSI design components, which usually form the leaf components in the VLSI design hierarchy. In the following, we will refer to leaf components as "leafs". For detailed definitions of hierarchy, VLSI design components, nets, etc., see U.S. Pat. Nos. 5,519,628 and 5,481,473 and the reference materials, Introduction to Algorithms, by T. H. Corment, C. E. Leiserson, R. L. Rivest (MIT Press), hereafter referred to as "Algorithms", and The LEDA Platform for Combinatorial and Geometric Computing, by K. Mehlhom, and S. Naher (Cambridge University Press), hereafter referred to as "Geometric Computing".
"Algorithms" shows that the single source shortest path problem can be solved with a Breadth First Search (BFS) in O(N) time in unweighted graphs. In a hierarchical design, the standard shortest path search in unweighted and undirected graphs, BFS, cannot be applied directly without flattening the design. Flattening the design before processing results in unprocessable amounts of data for large designs.
BFS requires at least two Boolean values (representable as two bits in a computer memory) per instance of a leaf (i.e., per vertex), which indicate whether or not the vertex was unprocessed, touched or visited. A vertex was is called visited if its outgoing edges were investigated during the BFS. It is called touched if it was found by investigating an outgoing edge of another vertex. In a shortest path search in a hierarchical design at least these Boolean variables must be stored for each instance of a leaf, i.e., flat, even when the design is not flattened before processing.